package 背包问题;

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;

/**
 * 最长公共子序列
 * leetcode url https://leetcode.cn/problems/longest-common-subsequence/
 */
public class Solution516 {
    public static void main(String[] args) {
        String text1 = "abcdef";
        int i = longestPalindromeSubseq1(text1);
        System.out.println(i);

        int j = longestPalindromeSubseq2(text1);

        System.out.println(j);
        ConcurrentHashMap concurrentHashMap=new ConcurrentHashMap();
        concurrentHashMap.put("1",1);
        concurrentHashMap.put("2",1);
        System.out.println(concurrentHashMap.size());

    }

    public static int longestPalindromeSubseq1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        return process(chars, 0, chars.length - 1);

    }

    public static int longestPalindromeSubseq2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        return dp(chars, 0, chars.length - 1);

    }

    //获取从字符l到r位置上的最长公共子序列
    public static int process(char[] str, int l, int r) {
        //base
        if (l == r) {
            return 1;
        }
        if (l == r - 1) {
            //左边=右边-1相等即 aa/ab 这样可能存在长度2和1的情况
            return str[l] == str[r] ? 2 : 1;
        }
        //不包含l位置，不包含r位置
        int p1 = process(str, l + 1, r - 1);
        //包含l位置，不包含r位置
        int p2 = process(str, l, r - 1);
        //不包含l位置，包含r位置
        int p3 = process(str, l + 1, r);
        //包含l位置 ，包含r位置
        int p4 = str[l] == str[r] ? 2 + process(str, l + 1, r - 1) : 0;
        return Math.max(p1, Math.max(p2, Math.max(p3, p4)));
    }


    //获取从字符l到r位置上的最长公共子序列
    public static int dp(char[] str, int l, int r) {
        //base
        int N = str.length;

        int[][] dp = new int[N][N];
        for (int i = 0; i < N; i++) {
            dp[i][i] = 1;
        }
        for (int i = 0; i < N - 1; i++) {
            for (int j = N - 1; j > i; j--) {
                if (i == j - 1) {
                    dp[i][j] = str[i] == str[j] ? 2 : 1;
                }
            }
        }
        for (int index = N - 3; index >= 0; index--) {
            for (int rset = index + 2; rset < N; rset++) {
                int p1 = dp[index + 1][rset - 1];
                int p2 = dp[index][rset - 1];
                int p3 = dp[index + 1][rset];
                int p4 = str[index] == str[rset] ? 2 + dp[index + 1][rset - 1] : 0;
                int max = Math.max(p1, Math.max(p2, Math.max(p3, p4)));
                dp[index][rset] = max;
            }
        }
        return dp[0][N - 1];
    }
}
